/*
 *  ConcatenationRope.java
 *  Copyright (C) 2007 Amin Ahmad.
 *
 *  This file is part of Java Ropes.
 *
 *  Java Ropes is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  Java Ropes is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Java Ropes.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  Amin Ahmad can be contacted at amin.ahmad@gmail.com or on the web at
 *  www.ahmadsoft.org.
 */
package org.ahmadsoft.ropes.impl;

import java.io.IOException;
import java.io.Writer;
import java.util.Iterator;

import org.ahmadsoft.ropes.Rope;

/**
 * A rope that represents the concatenation of two other ropes.
 * @author Amin Ahmad
 */
public final class ConcatenationRope extends AbstractRope {

    private final Rope left;
    private final Rope right;
    private final byte depth;
    private final int length;

    /**
     * Create a new concatenation rope from two ropes.
     * @param left the first rope.
     * @param right the second rope.
     */
    public ConcatenationRope(final Rope left, final Rope right) {
        this.left   = left;
        this.right  = right;
        this.depth  = (byte) (Math.max(RopeUtilities.INSTANCE.depth(left), RopeUtilities.INSTANCE.depth(right)) + 1);
        this.length = left.length() + right.length();
    }

//    public char charAt(final int index) {
//        if (index >= this.length())
//            throw new IndexOutOfBoundsException("Rope index out of range: " + index);
//
//        return (index < this.left.length() ? this.left.charAt(index): this.right.charAt(index - this.left.length()));
//    }


	public char charAt(final int index) {
		ConcatenationRope node = this;
		int nodeStart = 0;

		while (true) {
			Rope left = node.left;

			// keep locally for speed
			int ll = left.length();
			// the end of left child in absolute value (relative to root)
			int absoluteLeftEnd = ll + nodeStart;
			if (index < absoluteLeftEnd) {
				// character in left
				if (left instanceof ConcatenationRope) {
					// leaf in left branch
					node = (ConcatenationRope) left;
					continue;
				} else {
					// left is a leaf, finish here
					return left.charAt(index - nodeStart);
				}
			} else {
				// character in right
				Rope right = node.right;
				if (right instanceof ConcatenationRope) {
					// leaf in right branch
					node = (ConcatenationRope) right;
					nodeStart += ll;
					continue;
				} else {
					// right is a leaf, finish here
					return right.charAt(index - absoluteLeftEnd);
				}
			}
		}
	}
	
	
    @Override
	public int indexOf(char ch) {
		int index = left.indexOf(ch);
		if (index >= 0)
			return index;

		// Not found in left
		index = right.indexOf(ch);
		if (index >= 0)
			return index + left.length();

		return -1;
	}
	
	@Override
	public int indexOf(final char ch, final int fromIndex) {
		if (fromIndex < 0 || fromIndex >= this.length())
			throw new IndexOutOfBoundsException("Rope index out of range: " + fromIndex);
		
		final int ll = left.length();
		if (fromIndex < ll) {
			int lIndex = left.indexOf(ch, fromIndex);
			if (lIndex >= 0)
				return lIndex;
		}
		// CASES:
		// 1. Not found in left
		// 2. Index is beyond left length
		int rIndex = Math.max(0, fromIndex - ll);
		int result = right.indexOf(ch, rIndex);
		if (result >= 0)
			return result + ll;

		return -1;
	}
    
	/**
	 * This implementation assumes child ropes can performs the search
	 * faster than the Concatenation rope, so it tries to delegate to
	 * the children as soon as possible.
	 */
	@Override
	public int indexOf(final CharSequence str, int fromIndex) {
		final int strlen = str.length();
		final int lastPossibleIndex = this.length - strlen;

		if (fromIndex > lastPossibleIndex)
			// too long or index too high
			return -1;

		if (strlen == 1)
			return indexOf(str.charAt(0), fromIndex);
		
		final int ll = left.length();
		
		// right optimization
		if (fromIndex >= ll){
			// index too big for left. Go straight to right
			int rIndex = right.indexOf(str, fromIndex - ll);
			if (rIndex >= 0)
				return rIndex + ll;
			else 
				return -1;
		}
		
		// left optimization
		if (ll > fromIndex + strlen){
			// left optimization, check if the sequence is there. If it is we can finish early.
			int lIndex = left.indexOf(str, fromIndex);
			if (lIndex >= 0)
				return lIndex;
			// not found, we can advance the index to the part of the left that does not contain the string.
			fromIndex = ll - strlen;
		}
		
		// full search
		final char firstChar = str.charAt(0);
		ConcatenationRopeSequentialAccess sequence = null; 
		
		int first;
		while ((first = indexOf(firstChar, fromIndex)) >= 0){
			// found too close to the end of the sequence
			if (first > lastPossibleIndex)
				return -1;

			// right optimization
			// instead of continuing the search loop, go directly to child.
			if (first >= ll){
				// index too big for left. Go straight to right
				int rIndex = right.indexOf(str, first - ll);
				if (rIndex >= 0)
					return rIndex + ll;
				else
					return -1;
			}
			
			boolean found = true;
			// first found, check the rest
			if (sequence == null)
				sequence = new ConcatenationRopeSequentialAccess(this);
			
			for (int i = strlen - 1; i >= 1; i--) {
				if (sequence.charAt(first + i) != str.charAt(i)){
					// not found, try next match
					found = false;
					break;
				}
			}
			if (found)
				return first;
			
			// advance index to this match
			fromIndex = first + 1;
		}
		return -1;
	}

    @Override
    public byte depth() {
        return this.depth;
    }

    @Override
    public CharSequence getForSequentialAccess() {
    	return new ConcatenationRopeSequentialAccess(this);
    }

    
    
    /*
     * Returns this object as a char sequence optimized for
     * regular expression searches.
     * <p>
     * <emph>This method is public only to facilitate unit
     * testing.</emph>
     */
    private CharSequence getForSequentialAccess(final Rope rope) {
        return new CharSequence() {

            private final ConcatenationRopeIteratorImpl iterator = (ConcatenationRopeIteratorImpl) rope.iterator(0);

            public char charAt(final int index) {
                if (index > this.iterator.getPos()) {
                    this.iterator.skip(index-this.iterator.getPos()-1);
                    try {
                        final char c = this.iterator.nextChar();
                        return c;
                    } catch (final IllegalArgumentException e) {
                        System.out.println("Rope length is: " + rope.length() + " charAt is " + index);
                        throw e;
                    }
                } else { /* if (index <= lastIndex) */
                    final int toMoveBack = this.iterator.getPos() - index + 1;
                    if (this.iterator.canMoveBackwards(toMoveBack)) {
                        this.iterator.moveBackwards(toMoveBack);
                        return this.iterator.nextChar();
                    } else {
                        return rope.charAt(index);
                    }
                }
            }

            public int length() {
                return rope.length();
            }

            public CharSequence subSequence(final int start, final int end) {
                return rope.subSequence(start, end);
            }

        };
    }

    /**
     * Return the left-hand rope.
     * @return the left-hand rope.
     */
    public Rope getLeft() {
        return this.left;
    }

    /**
     * Return the right-hand rope.
     * @return the right-hand rope.
     */
    public Rope getRight() {
        return this.right;
    }

    public Iterator<Character> iterator(final int start) {
        if (start < 0 || start > this.length())
            throw new IndexOutOfBoundsException("Rope index out of range: " + start);
        if (start >= this.left.length()) {
            return this.right.iterator(start - this.left.length());
        } else {
        	return new CharSequenceIterator(getForSequentialAccess(), start);
        }
    }

    public int length() {
        return this.length;
    }

    public Rope rebalance() {
        return RopeUtilities.INSTANCE.rebalance(this);
    }

    public Rope reverse() {
        return RopeUtilities.INSTANCE.concatenate(this.getRight().reverse(), this.getLeft().reverse());
    }

    public Iterator<Character> reverseIterator(final int start) {
        if (start < 0 || start > this.length())
            throw new IndexOutOfBoundsException("Rope index out of range: " + start);
        if (start >= this.right.length()) {
            return this.left.reverseIterator(start - this.right.length());
        } else {
            return new ConcatenationRopeReverseIteratorImpl(this, start);
        }
    }

    public Rope subSequence(final int start, final int end) {
        if (start < 0 || end > this.length())
            throw new IllegalArgumentException("Illegal subsequence (" + start + "," + end + ")");
        if (start == 0 && end == this.length())
            return this;
        final int l = this.left.length();
        if (end <= l)
            return this.left.subSequence(start, end);
        if (start >= l)
            return this.right.subSequence(start - l, end - l);
        return RopeUtilities.INSTANCE.concatenate(
            this.left.subSequence(start, l),
            this.right.subSequence(0, end - l));
    }

    public void write(final Writer out) throws IOException {
        this.left.write(out);
        this.right.write(out);
    }

    public void write(final Writer out, final int offset, final int length) throws IOException {
        if (offset + length <= this.left.length()) {
            this.left.write(out, offset, length);
        } else if (offset >= this.left.length()) {
            this.right.write(out, offset - this.left.length(), length);
        } else {
            final int writeLeft = this.left.length() - offset;
            this.left.write(out, offset, writeLeft);
            this.right.write(out, 0, length - writeLeft);
        }
    }
    

//  /**
//   * Not currently used. Can be used if rebalancing is performed
//   * during concatenation.
//   **/
//  private ConcatenationRope rotateLeft(final ConcatenationRope input) {
//      final Rope _R = input.getRight();
//      if (!(_R instanceof ConcatenationRope))
//          return input;
//      final ConcatenationRope R = (ConcatenationRope) _R;
//      final Rope L = input.getLeft();
//      final Rope A = R.getLeft();
//      final Rope B = R.getRight();
//      return new ConcatenationRope(new ConcatenationRope(L, A), B);
//  }
//
//  /**
//   * Not currently used. Can be used if rebalancing is performed
//   * during concatenation.
//   **/
//  private ConcatenationRope rotateRight(final ConcatenationRope input) {
//      final Rope _L = input.getLeft();
//      if (!(_L instanceof ConcatenationRope))
//          return input;
//      final ConcatenationRope L = (ConcatenationRope) _L;
//      final Rope R = input.getRight();
//      final Rope A = L.getLeft();
//      final Rope B = L.getRight();
//      return new ConcatenationRope(A, new ConcatenationRope(B, R));
//  }
}
